Video applications can be computationally expensive. Designers may attempt to compress video data to reduce the workload associated with video data. For example, designers may use compression algorithms that take advantage of the high degree of correlation between successive video frames. One such technique is motion estimation. With motion estimation, a reference image (e.g., a previously encoded frame) is sub-divided into macroblocks of 16×16 pixels. The encoding algorithm attempts to match this macroblock to another macroblock that is in a search window in another image (e.g., a current frame). When the best match is obtained, the motion vector that captures the movement of the macroblock from the reference frame to the current frame is encoded and transmitted in place of the actual block.
A method used for determining whether two blocks match one another is the Sum-of-Absolute Differences (SAD). For every search step within the search window of a macroblock in the reference frame, the SAD for the 256 pixels of the block (Σ256|ai−bi|) is computed. The search may continue until the best match (i.e., lowest SAD) is obtained. This operation may repeat for every macroblock in the reference frame. For high resolution video (e.g., 1920×1080 pixels at 30 frame/sec), the method requires computing the motion vector for 243,000 macroblocks/second. Consequently, motion estimation is computationally expensive.